package LeetcodeTest_fifteen;
//二叉树的层次遍历

import java.util.*;
public class levelOrderBottom
{
    public static void main(String[] args)
    {
        TreeNode root=null;
        root=Solution.createTree(root);
        List<List<Integer>> a=new ArrayList<List<Integer>>();
        a=Solution.levelOrderBottom(root);
        for(int i=0;i<a.size();i++)
            System.out.println(a.get(i));
    }
}
class Solution
{
    public static List<List<Integer>> levelOrderBottom(TreeNode root)
    {
        if(root==null)
            return null;
        List<List<Integer>> answer1= new ArrayList<List<Integer>>();//保存最终结果
        List<List<Integer>> answer2= new ArrayList<List<Integer>>();//结果反转
        ArrayList<Integer> result=new ArrayList<Integer>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();//将节点存到队列
        int curr,next,x;
        curr=x=1;//当前层的节点数量
        next=0;//下一层的节点数量
        queue.offer(root);
        while(!queue.isEmpty())
        {
            TreeNode tree=queue.poll();
            curr--;
            if(tree.left!=null)
            {
                queue.offer(tree.left);
                next++;
            }
            if(tree.right!=null)
            {
                queue.offer(tree.right);
                next++;
            }
            result.add(tree.val);
            if(curr==0)
            {
                List<Integer> layer=new ArrayList<Integer>();
                for(int i=result.size()-x;i<result.size();i++)
                    layer.add(result.get(i));
                answer1.add(layer);
                curr=x=next;
                next=0;
            }
        }
        for(int j=answer1.size()-1;j>=0;j--)
            answer2.add(answer1.get(j));
        return answer2;
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
}
class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}